Elle s’appelle liste chainée simple parce qu’il n’y que le sens avancer. La double va dans les deux sens, avancer et reculer.
class Cellule:
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
class ListeSimplementChainee:
def __init__(self):
self.tete = None
self.queue = None
self.taille = 0On peut tout mettre dans un générateur, afin de pouvoir parcourir la liste chaînée avec un for dans le reste des fonctions. On évite aussi la création d’un tableau intermédiaire.
def recupere_cellules(liste_chainee):
cellule_courante = liste_chainee.tete
while cellule_courante:
yield cellule_courante
cellule_courante = cellule_courante.suivantOn rattache la liste à une nouvelle cellule, et elle devient la tête. Temps O(1).
def ajoute_en_tete(liste_chainee, valeur):
liste_chainee.tete = Cellule(valeur, liste_chainee.tete)
if liste_chainee.taille == 0:
liste_chainee.queue = liste_chainee.tete
liste_chainee.taille += 1
return liste_chaineeLa cellule en queue pointe vers une nouvelle cellule. Temps O(1).
def ajoute_en_queue(liste_chainee, valeur):
nouvelle_cellule = Cellule(valeur)
if liste_chainee.taille == 0:
liste_chainee.tete = nouvelle_cellule
else:
liste_chainee.queue.suivant = nouvelle_cellule
liste_chainee.queue = nouvelle_cellule
liste_chainee.taille += 1
return liste_chaineeOn aura besoin d’un pointeur sur le précedant pour “relier” la chaîne. On utilise courant pour identifier la cellule à supprimer et precedant pour relier. On relie en utilisant le suivant de la cellule à supprimer.
La suppression demande un parcours de liste en O(n).
def supprime_suivant(liste_chainee, cellule):
if cellule:
supprimee = cellule.suivant
cellule.suivant = supprimee.suivant
else: # Pas de précédant => on est en tête de liste
supprimee = liste_chainee.tete
liste_chainee.tete = supprime.suivant
def supprime(liste_chainee, valeur):
precedant = None
courant = None
for cellule in recupere_cellules(liste_chainee):
courant = cellule
if courant.valeur == valeur:
supprime_suivant(liste_chainee, precedant)
precedant = courant
return liste_chaineeLa liste boucle sur elle même, et on a une cellule sentinelle pour marquer à la fois le début et la fin de la liste.
C’est un élément bidon, mais pratique: au lieu de gérer les cas début de liste/fin de liste comme au dessus, quand on boucle ça marche tout le temps. Le reste c’est la même chose.
def recupere_cellules(liste_chainee):
cellule_courante = liste_chainee.tete.suivant
while cellule_courante is not liste_chainee.tete:
yield cellule_courante
cellule_courante = cellule_courante.suivantDessus, on aura des methodes enqueue() pour l’ajout, dequeue() pour récupérer.
Dessus, on aura des methodes push() pour l’ajout, pop() pour récupérer.
Des petits trucs pour aller plus vite en TP et contrôle.
{} est converti en string.__str__.class Cellule:
"""Une cellule d'une liste."""
def __init__(self, valeur, suivant=None):
self.valeur = valeur
self.suivant = suivant
def __str__(self):
return f'<Cellule valeur={self.valeur}>'
cell = Cellule(10)
print(f'cell: {cell}')cell: <Cellule valeur=10>
enumeratewhile avec accès au i direct.break.Avec un tableau:
tableau = ['a', 'b', 'c']
for i, valeur in tableau:
print(f'Valeur {i}: {valeur}')Valeur 0: a
Valeur 1: b
Valeur 2: c
Avec un générateur:
def gen_jours():
"""Générateur qui renvoie les jours de travail de la semaine."""
yield "Lundi"
yield "Mardi"
yield "Mercredi"
yield "Jeudi"
yield "Vendredi"
for i, jour in enumerate(gen_jours()):
print(f'Jour {i}: {jour}')
if i == 2:
breakJour 0: Lundi
Jour 1: Mardi
Jour 2: Mercredi
str.join()print(" | ".join(['a', 'b', 'c', 'd', 'e']))
print("\n".join(["ligne 1", "ligne 2", "ligne 3"]))a | b | c | d | e
ligne 1
ligne 2
ligne 3